#lang sicp
(define (in-count-pairs x)
  (if (not (pair? x))
      0
      (+ 1
         (in-count-pairs (car x))
         (in-count-pairs (cdr x)))))

(define a (cons 1 2))
(define b (cons a a))

(define three (list 1 a))
(define four (list a a))
(define seven (cons b b))



;; 3.17
(define (count-pairs x)
  (define records (make-records))
  (define (iter x)
    (if (not (pair? x))
        0
        (if (records 'met? x)
            0
            (+ 1
               (iter (car x))
               (iter (cdr x))))))
  (iter x))

(define (make-records)
  (define data (list))
  (define add! (lambda (x)
                 (set! data (cons x data))))
  (define has? (lambda (x)
                 (define (iter se)
                   (cond ((null? se) #F)
                         ((eq? (car se) x) #T)
                         (else (iter (cdr se)))))
                 (iter data)))
  (define met? (lambda (x)
                 (if (has? x)
                     #T
                     (begin (add! x)
                            #F))))
  (define (dispatch msg)
    (cond ((eq? msg 'met?) met?)
          ((eq? msg 'has?) has?)
          ((eq? msg 'add!) add!)
          (else (error "unkonwn message! -- MAKE-RECORDS" msg))))
  (lambda (msg . args)
    (apply (dispatch msg) args)))


(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define (examine-cycle x)
  (define records (make-records))
  (define (iter se)
    (cond ((null? se) #F)
          ((records 'met? (car se)) #T)
          (else (iter (cdr se)))))
  (iter x))


(define cycle1 (make-cycle (list 1 2 3 4)))


(define (test-cycle x)
  (define (iter fast slow)
    (if (or (null? fast) (null? (cdr fast)))
        #F
        (let ((fast (cdr (cdr fast)))
              (slow (cdr slow)))
          (if (eq? fast slow)
              #T
              (iter fast slow)))))
  (iter x x))